<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 动态规划--空间优化
        /* 
            O(n)
            O(2 * k + 1)
        */
        var maxProfit = function(prices, k) {
            // 初始化
            let dp = new Array(2 * k + 1).fill(0)
            for (let j = 1; j < 2 * k; j+=2) {
                dp[j] = -prices[0]
            }
            let totalProfit = 0; // 初始化总利润为0
            // 下面两种方式都行
            for (let i = 1; i < prices.length; i++) { // 遍历每一天的股票作为买卖时机
                for (let j = 0; j < 2 * k - 1; j+=2) { // j=0时处理1和2，j=1时，处理3和4
                    // 类比奇数是买 偶数是卖
                    dp[j + 1] = Math.max(dp[j + 1], dp[j] - prices[i])
                    dp[j + 2] = Math.max(dp[j + 2], dp[j + 1] + prices[i])
                }
            }
            // for (let i = 1; i < prices.length; i++) { // 遍历每一天的股票作为买卖时机
            //     for (let j = 1; j < 2 * k + 1; j++) { // j=0时处理1和2，j=1时，处理3和4
            //         // 类比奇数是买 偶数是卖
            //         // dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i])
            //         // dp[i][j + 2] = Math.max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i])
            //         // 奇数 买入
            //         if (j % 2) {
            //           dp[j] = Math.max(dp[j], dp[j - 1] - prices[i])
            //         } else {
            //           dp[j] = Math.max(dp[j], dp[j - 1] + prices[i])
            //         }
            //     }
            // }
            return dp[2 * k]; // 返回总利润
        };
        console.log(maxProfit([3,2,6,5,0,3], 2));
        // console.log(maxProfit([1,2,3,4,5], 2));
    </script>
</body>

</html>